package com.explorati.LeetCode167.twosum2;

import java.util.Arrays;

/**
 * 167. Two Sum II - Input array is sorted 解法二：使用二分查找法
 * 
 * @author explorati
 *
 */
public class Solution1 {
	public static int[] twoSum(int[] numbers, int target) {
		int arr[] = new int[2];
		// 从i开始向后中查找
		for (int i = 0; i < numbers.length; i++) {
			int j = numbers.length - 1;
			int mid = (i + j) / 2;
			while (numbers[i] + numbers[j] > target && mid >= i && mid <= target) {
				// 如果中间位置元素和i加和大于target
				if (numbers[mid] + numbers[i] > target) {
					mid = (mid + j) / 2;
				} else if (numbers[mid] + numbers[i] == target) {
					// 去除相等索引
					if (mid == i) {
						break;
					}
					arr[0] = i + 1;
					arr[1] = mid + 1;
					return arr;
				} else {
					mid = (i + mid) / 2;
				}
			}
		}
		return arr;
	}

	public static void main(String[] args) {
		int[] numbers = { 2, 7, 9, 22 };
		int[] arr = twoSum(numbers, 9);
		for (int i : arr) {
			System.out.print(i + "  ");
		}
	}

}
